package class8;

import common.TreeNode;
import common.TreeNodeUtils;

import java.util.Stack;

/**
 * 非递归方式遍历二叉树
 * pre先序遍历
 */
public class Code02_BinaryTreeStack {
    public static void main(String[] args) {
        TreeNode root = getTreeNode();

        preOrder(root);
        midOrder(root);
//        posOrder(root);

        //
        preOrder2(root);
    }

    /**
     * 先序遍历1：
     * 需要先将右节点压栈，因为出栈时，是左节点先出
     */
    private static void preOrder(TreeNode root) {
        System.out.println("pre-order:");
        if (root != null) {
            Stack<TreeNode> stack = new Stack<>();
            stack.add(root);
            while (!stack.isEmpty()) {
                // 1.先弹出头
                TreeNode head = stack.pop();
                System.out.print(head.val + "\t");
                // 2.再压右
                if (head.right != null) {
                    stack.push(head.right);
                }
                // 3. 再压入左
                if (head.left != null) {
                    stack.push(head.left);
                }
                // 弹出顺序为：头 - > 左 -> 右 (先序遍历)
            }
        }
        System.out.println();
    }

    /**
     * 数组实现栈
     */
    private static void preOrder2(TreeNode root) {
        TreeNode[] stack = new TreeNode[100];
        int r = 0;
        if (root != null) {
            stack[r++] = root;
            while (r > 0) {
                TreeNode pop = stack[--r];
                System.out.print(pop.val + "\t");
                if (pop.right != null) {
                    stack[r++] = pop.right;
                }
                if (pop.left != null) {
                    stack[r++] = pop.left;
                }
            }
        }
    }

    /**
     * 后序遍历2：
     * 需要先压栈左节点，然后借助另一个栈实现打印
     */
    private static void posOrder(TreeNode root) {
        if (root != null) {
            System.out.println("pos-order: ");
            Stack<TreeNode> stack = new Stack<>();
            Stack<TreeNode> stack2 = new Stack<>();
            stack.add(root);
            while (!stack.isEmpty()) {
                // 1.先弹出头
                TreeNode head = stack.pop();
                stack2.add(head);
                // 2.先压左
                if (head.left != null) {
                    stack.push(head.left);
                }
                // 3.再压右
                if (head.right != null) {
                    stack.push(head.right);
                }
                // 弹出顺序：头 -> 右 -> 左
                // 再压入另一个栈，出栈的顺序变为：左、右、头 (后序遍历)
            }

            while (!stack2.isEmpty()) {
                System.out.print(stack2.pop().val + "\t");
            }

        }
    }

    /**
     * 中序遍历
     * 1.将左边一直进栈，直到没有左节点为止
     * 2.出栈右节点，打印
     * 3.再将右子跟着继续走，
     */
    private static void midOrder(TreeNode cur) {
        System.out.println("mid-order:");
        if (cur != null) {
            Stack<TreeNode> stack = new Stack<>();
            while (!stack.isEmpty() || cur != null) {
                if (cur != null) {
                    stack.push(cur);  // 1. 将当前节点入栈
                    cur = cur.left; // 2. 移动到左子节点
                } else {
                    cur = stack.pop(); // 3. 栈顶元素出栈，访问该节点
                    System.out.print(cur.val + "\t");  // 4. 打印节点值
                    cur = cur.right;  // 5. 转到右子节点
                }
            }
        }
        System.out.println();
    }


    private static TreeNode getTreeNode() {
        /**
         *          1
         *         2 3
         *       4 5  6 7
         *         8 9 10
         *
         */
        TreeNode treeNode1 = TreeNodeUtils.createTreeNode(1, 2, 3);
        TreeNode left = treeNode1.left;
        TreeNode right = treeNode1.right;
        TreeNode[] t3 = TreeNodeUtils.getTreeNodes(4, 5, 6, 7);
        TreeNode[] t4 = TreeNodeUtils.getTreeNodes(8, 9, 10);

        left.left = t3[0];
        left.right = t3[1];
        right.left = t3[2];
        right.right = t3[3];

        t3[1].left = t4[0];
        t3[2].left = t4[1];
        t3[2].right = t4[2];
        return treeNode1;
    }

}
